#include<iostream>
#include<queue>
#include<list>
#include<deque>
using namespace std;

namespace my_priority_queue  
{  
	// 定义一个模板类priority_queue，其中T是元素类型，container是容器类型（默认为vector<T>），compare是比较函数（默认为std::less<T>）  
	template<class T, class container = std::vector<T>, class compare = std::less<T>>  
	class priority_queue  
	{  
	public:  
		// 构造函数，接收一个比较函数和容器的默认参数  
		priority_queue(const compare& com = compare(), const container& con = container()) : com_(com), con_(con)  
		{  
			// 初始化成员变量com_和con_  
		}  
  
		// 判断优先队列是否为空  
		bool empty() const  
		{  
			return con_.empty();  
		}  
  
		// 返回优先队列的大小  
		size_t size() const  
		{  
			return con_.size();  
		}  
  
		// 获取优先队列的顶部元素（非const版本）  
		T& top()   
		{  
			return con_.front();  
		}  
  
		// 获取优先队列的顶部元素（const版本）  
		const T& top() const  
		{  
			return con_.front();  
		}  
  
		// 向优先队列中推入一个元素  
		void push(const T& val)  
		{  
			con_.push_back(val); // 将元素添加到容器的末尾  
			push_heap(con_.begin(), con_.end(), com_); // 使用push_heap函数调整堆结构  
		}  
  
		// 从优先队列中弹出一个元素  
		void pop()  
		{  
			std::swap(*(con_.begin()), *(--con_.end())); // 交换堆顶元素和最后一个元素  
			con_.pop_back(); // 删除最后一个元素（原堆顶元素）  
			pop_heap(con_.begin(), con_.end(), com_); // 使用pop_heap函数重新调整堆结构  
		}  
  
	private:  
		// 向上调整堆的辅助函数（用于push操作后）  
		template<class RandomAccessIterator>  
		void push_heap(RandomAccessIterator first, RandomAccessIterator last, compare com)  
		{  
			// 计算容器的大小  
			int size_ = 0;  
			RandomAccessIterator cur = first;  
			while (cur != last)  
			{  
				cur++;  
				size_++;  
			}  
  
			// 从最后一个元素的父节点开始向上调整  
			int parent = (size_ - 1) / 2; // 最后一个元素的父节点索引  
			int child = size_ - 1; // 最后一个元素的索引  
  
			// 向上调整堆  
			while (parent >= 0)  
			{  
				if (com(*(first + parent), *(first + child)))  
				{  
					std::swap(*(first + parent), *(first + child));  
					child = parent;  
					parent = (child - 1) / 2;  
				}  
				else  
				{  
					break;  
				}  
			}  
		}  
  
		// 向下调整堆的辅助函数（用于pop操作后）  
		template<class RandomAccessIterator>  
		void pop_heap(RandomAccessIterator first, RandomAccessIterator last, compare comp)  
		{  
			// 计算容器的大小  
			int size_ = 0;  
			RandomAccessIterator cur = first;  
			while (cur != last)  
			{  
				cur++;  
				size_++;  
			}  
  
			// 从根节点开始向下调整  
			int parent = 0; // 根节点的索引  
			int child = parent * 2 + 1; // 左子节点的索引  
  
			// 向下调整堆  
			while (child < size_)  
			{  
				// 找到左右子节点中较大的一个  
				if (child + 1 < size_ && comp(*(first + child), *(first + child)))
				{
					std::swap(*(first + parent), *(first + child));
					parent = child;
					child = parent * 2 + 1;
				}

				else
				{
					break;
				}
			}
		}
		container con_;
		compare com_;
	};
}